package de.hsb.ai.agent.TeamDetectiveAgent;

import game.Move;

import java.util.List;
import java.util.Set;
import java.util.Vector;

import org.jgrapht.Graphs;

import de.hsb.ai.util.map.ScotlandJadeMap;
import de.hsb.ai.util.map.ScotlandJadeMapHelper.ScotlandJadeEdge;
import de.hsb.ai.util.map.ScotlandJadeMapHelper.ScotlandJadeVertex;
import de.hsb.ai.util.map.ScotlandJadeMapHelper.ScotlandJadeVertex.Type;

/**
 * Class for calculation of the best move for the current TeamDetective.
 */
public class HuntPreparation {

//	Measures the distance to the next metro. Used within the first three moves of the game. 
	int distanceToMetro;
//	Value for the turn of the TeamDetective, which is the game round.
	int turn;
//	Object for all operations regarding the current map, with its player positions.
	ScotlandJadeMap map;
//	Object for all distance measurement purposes.
	DistanceFinder df;
//	Object with the current TeamDetective.
	TeamDetective td;
//	List of possible moves of the current detective.
	List<Move> options;
//	Last position of the fugitive.
	int lastKnownFugitivePosition;
//	Current amount of detectives tickets.
	int [] detTickets;
//	The tree of nodes for the MinMax-Search.
	Vector<TDNode> nodes = new Vector<TDNode>();
//	Current level(depth) in the MinMax-Search.
	int level = 0;

	/**
	 * Constructor
	 * 
	 * @param map
	 * @param td
	 * @param options
	 * @param turn
	 */
	public HuntPreparation(ScotlandJadeMap map, TeamDetective td,
			List<Move> options, int turn, int lastKnownFugitivePosition,  int[] ticket) {
		this.td = td;
		this.map = map;
		df = new DistanceFinder(map);
		this.options = options;
		this.turn = turn;
		this.lastKnownFugitivePosition = lastKnownFugitivePosition;
		this.detTickets = ticket;
	}

	/**
	 * Main method of this class. It gets called by TeamDetective - the 
	 * main class of this AI-Implementation and returns the final decision 
	 * after everything is calculated.
	 * @return Move: This return value says where the detective will go this
	 *         round.
	 */
	public Move getMove() {
		System.out.println("Round: "+td.getRound());
		// current detective
		ScotlandJadeVertex detectivePos = td.getCurrentDetectivePosition(options);
//		AI for the first 3 rounds.
		if(turn < 3){
			// This Vertex represents the Vertex to which the detective should go
			ScotlandJadeVertex go;
			// To decide where to go the method "findClosestMetro()" is called.
			go = findClosestMetro();
//			TODO
//			Choose bette edge.
//			Set<ScotlandJadeEdge> twoEdges = map.getAllEdges(detectivePos, go);
//			Object[] edge = twoEdges.toArray();
//			Move m;
//			if(edge.length > 1){
//				m = chooseBetterEdge(edge, go);
//				if(m != null){
//					return m;
//				}
//			}
			// Find the node in the "options" list and return it.
			for (int w = 0; w < options.size(); w++) {
				if (options.get(w).getNode() == go.getIndex()) {
					return options.get(w);
				}
			}
//		AI after the first 3 rounds.
		}else{
			ScotlandJadeVertex decision;
			decision = minMax();
//			TODO
//			Choose bette edge.
//			Set<ScotlandJadeEdge> twoEdges = map.getAllEdges(detectivePos, decision);
//			Object[] edge = twoEdges.toArray();
//			Move m;
//			if(edge.length > 1){
//				m = chooseBetterEdge(edge, decision);
//				if(m != null){
//					return m;
//				}
//			}
			for (int w = 0; w < options.size(); w++) {
				if (options.get(w).getNode() == decision.getIndex()) {
					System.out.println("Move "+options.get(w));
					return options.get(w);
				}
			}
		}
		return saveMove(options);
	}

	/**
	 * Method for saving important tickets.
	 * If there are multiple ways to a goal, the cheaper one gets chosen.
	 */
	private Move chooseBetterEdge(Object[] edge, ScotlandJadeVertex go) {
		int setType = 0;
		int whichType = 0;
		for (int j = 0; j < edge.length; j++) {
			ScotlandJadeEdge sj = (ScotlandJadeEdge) edge[j];
			if(whichType < sj.getType()){
				whichType = sj.getType();
			}
		}
		
		// if the detective can use a  metro or a bus
		if (whichType == 3){
			
			// and if the detective has more bus than metro tickets
			if(detTickets[2] >  detTickets[3]){
				setType = 2;
			}
			else{
				setType = 3;
			}
		}
		
		// if the detective can use a bus or a taxi
		if (whichType == 2){
			if (detTickets[1] > detTickets [2]){
				setType = 1;
			}
			else{
				setType = 2;
			}
		}
		
		// Find the node in the "options" list and return it.
		for (int w = 0; w < options.size(); w++) {
			if (options.get(w).getNode() == go.getIndex()) {
				options.get(w).setType(setType);
				return options.get(w);
			}
		}
		return null;
	}

	/**
	 * A move that gets calculated, when the detective needs to avoid the metro.
	 * This method saves important tickets and eliminates wrong decisions.
	 */
	private Move saveMove(List<Move> options) {
		System.out.println("saveMove");
		int lowest = 100;
		int index = 0;
		for (int i = 0; i < options.size(); i++) {
			if(options.get(i).getType() != 3){
				if(td.mrx.size() > 0){
					int currentDistance = df.getDistance(map.get(options.get(i).getNode()), td.mrx.get(0));
					if(currentDistance < lowest){
						lowest = currentDistance;
						index = i;
					}
				}
			}
		}
		return options.get(index);
	}

	/**
	 * Starts the MinMax calculation. The nodes on level 0 are added.
	 * Then for all even moves the max algorithm gets executed, for all uneven
	 * min gets executed. 
	 * 
	 * After finishing the maximum depth nodes, backtracking of the highest value 
	 * node starts. The position of the current detective of the backtracked node
	 * on level 1 will be returned as move.
	 * 
	 * @return returns the resulting move of the MinMax calculation.
	 */
	private ScotlandJadeVertex minMax() {
//		All possible positions of Mr. X that are worth tracing get saved.
		List<ScotlandJadeVertex> mrx = findMrX(true);
//		All nodes on level 0 get created. The only difference is the position of Mr. X.
		for (int i = 0; i < mrx.size(); i++) {
			Vector<ScotlandJadeVertex> detPositions = td.getDetectivePositions();
			ScotlandJadeVertex currentDet = td.getCurrentDetectivePosition(options);
			int currentDetIndex = -1;
//			Saves the detective that is on turn
			for (int j = 0; j < detPositions.size(); j++) {
				if(detPositions.get(j).getIndex() == currentDet.getIndex()){
					currentDetIndex = j;
				}
			}
//			Save the node that contains the current state.
			nodes.add(new TDNode(0, detPositions , mrx.get(i).getIndex(), null, 0, currentDetIndex, 0));
		}
		
//		Min and max get executed. 5 levels overall, all even levels are max.
		for (int i = 0; i < 4; i++) {
			level = i;
			if(i%2==0){
				max(mrx);
			}else{
				min();
			}
		}
		int bestNodeIndex = 0;
		int highestValue = 0;
//		Node that got the highest value in MinMax will be found.
		for (int i = 0; i < nodes.size(); i++) {
			if(nodes.get(i).getValuation() > highestValue){
				highestValue = nodes.get(i).getValuation();
				bestNodeIndex = i;
			}
			
//			if(nodes.get(i).getLevel() < 4){
//				System.out.println(("Detective: "+nodes.get(i).getDetectives().get(nodes.get(i).getCurrentDetective())));
//				System.out.println("Mr. X: "+nodes.get(i).getMrX());
//				System.out.println("Lvl: "+nodes.get(i).getLevel());
//				System.out.println("Valuation: "+nodes.get(i).getValuation());
//				System.out.println("-");
//			}
		}
		System.out.println("Current Detective "+td.getCurrentDetectivePosition(options) +" "+bestNodeIndex);
		TDNode n = nodes.get(bestNodeIndex);
		TDNode move = null;
		int pos = 0;
//		Backtracking till level 1 best node.
		while(n.getParent() != null){
			move = n;
			pos = move.getDetectives().get(move.getCurrentDetective()).getIndex();
			n = n.getParent();
		}
//		pos is level 1 best nodes position of the current detective.
		return map.get(pos);
	}

	/**
	 * Max starts the moves of detectives:
	 * Expands by one more level for each detective, the expansion is made for
	 * 		1. the best move that makes the detective come closer to a possible Mr. X position
	 * 		2. the best move that blocks an escape way of Mr. X
	 * Valuates the newly expanded nodes by three evaluation functions:
	 * 		reachedTarget, mrXEscaped, improvedPosition
	 */
	private void max(List<ScotlandJadeVertex> mrx) {
		for (int i = 0; i < nodes.size(); i++) {
			if(nodes.get(i).getLevel() == level && nodes.get(i).getValuation() == 0){
				Vector<ScotlandJadeVertex> detPositions = nodes.get(i).getDetectives();
				List<ScotlandJadeVertex> detTargets = Graphs.neighborListOf(map, map.get(1));
				Vector<ScotlandJadeVertex> newDetPositions1 = new Vector<ScotlandJadeVertex>();
				Vector<ScotlandJadeVertex> newDetPositions2 = new Vector<ScotlandJadeVertex>();
				detTargets.clear();
//				No two detectives on the same field or target.
				Vector<Integer> inUse = new Vector<Integer>();
//				the best move that makes the detective come closer to a possible Mr. X position
				for (int j = 0; j < detPositions.size(); j++) {
					detTargets.add(findTarget(detPositions.get(j), inUse));
					inUse.add(detTargets.get(detTargets.size()-1).getIndex());
				}
				for (int j = 0; j < detPositions.size(); j++) {
					newDetPositions1.add(map.get(moveTowards(detPositions.get(j), detTargets.get(j))));
				}
//				the best move that blocks an escape way of Mr. X
				inUse = new Vector<Integer>();
				detTargets.clear();
				for (int j = 0; j < detPositions.size(); j++) {
					detTargets.add(findSecondTarget(detPositions.get(j), inUse));
					inUse.add(detTargets.get(detTargets.size()-1).getIndex());
				}
				for (int j = 0; j < detPositions.size(); j++) {
					newDetPositions2.add(map.get(moveTowards(detPositions.get(j), detTargets.get(j))));
				}
				
//				First and most important valuation - can a Mr. X position be reached?
				int valuation = reachedTarget(nodes.get(nodes.size()-1).getDetectives().get(nodes.get(nodes.size()-1).getCurrentDetective()), map.get(nodes.get(nodes.size()-1).getMrX()));
//				TODO
				if(level != 2){
					if(valuation == -1){
						if(level != 0){
//							If no Mr. X position can be reached - could Mr. X be escaped?
							valuation = mrXEscaped(nodes.get(nodes.size()-1));
						}else{
							valuation = 0;
						}
					}
				}else{
//					If the maximum level is explored, valuate all new nodes.
					valuation = improvedPosition(nodes.get(nodes.size()-1));
				}
//				The actual node expansion with the values calculated before.
				if(level < 3){
					nodes.add(new TDNode(nodes.size(), newDetPositions1, nodes.get(i).getMrX(), nodes.get(i), 
							nodes.get(i).getLevel()+1, nodes.get(i).getCurrentDetective(), valuation));
//					TODO
					if(level == 0){
						newDetPositions1.clear();
						for (int k = 0; k < detPositions.size(); k++) {
							int move = moveTowards(detPositions.get(k), detTargets.get(k));
							if(k != nodes.get(i).getCurrentDetective()){
								newDetPositions1.add(map.get(move));
							}else{
								newDetPositions1.add(map.get(alternativeMoveOption(detPositions.get(k), detTargets.get(k), map.get(move))));
							}
						}
						nodes.add(new TDNode(nodes.size(), newDetPositions2, nodes.get(i).getMrX(), nodes.get(i), 
								nodes.get(i).getLevel()+1, nodes.get(i).getCurrentDetective(), valuation));
					}
				}
			}
		}
	}

	/**
	 * Starts the moves of Mr. X and expands by one level. 
	 * There is no valuation, because all possible positions of Mr. X could be right
	 * and thus get treated equally. 
	 */
	private void min() {
		for (int j = 0; j < nodes.size(); j++) {
			if(nodes.get(j).getLevel() == level){
				List<ScotlandJadeVertex> neighbours = Graphs.neighborListOf(map,  map.get(nodes.get(j).getMrX()));
				for (int k = 0; k < neighbours.size(); k++) {
//					TODO
					if(k<3){
						nodes.add(new TDNode(nodes.size(), nodes.get(j).getDetectives(), neighbours.get(k).getIndex(), nodes.get(j), nodes.get(j).getLevel()+1, nodes.get(j).getCurrentDetective(), 0));
					}
				}
			}
		}
	}
	
	/**
	 * Evaluation if Mr. X can run away from the most detectives.
	 * The parent node gets compared with the current.
	 * -101 = the comparison shows that Mr. X can increase all distances to detectives by his best move.
	 * -100 = the comparison shows that Mr. X can increase almost all distances to detectives by his best move.
	 */
	private int mrXEscaped(TDNode node){
		Vector<ScotlandJadeVertex> det = node.getDetectives();
		int mrx = node.getMrX();
		Vector<ScotlandJadeVertex> parentDet = node.getParent().getDetectives();
		int parentMrx = node.getParent().getMrX();
		boolean[] goAway = new boolean[parentDet.size()];
		for (int i = 0; i < det.size(); i++) {
			goAway[i] = df.getDistance(det.get(i), map.get(mrx)) > df.getDistance(parentDet.get(i), map.get(parentMrx));
		}
		int goAwayCounter = 0;
		for (int i = 0; i < goAway.length; i++) {
			if(goAway[i]){
				goAwayCounter++;
			}
		}
		int anzDetektive = det.size();
		if(goAwayCounter == anzDetektive){
			return -101;
		}else if(goAwayCounter == anzDetektive-1){
			return -100;
		}else{
			return 0;
		}
	}
	
	/**
	 * Executed for the deepest search level. Evaluates the current positions.
	 * Distances of all detectives to a possible position of Mr. X get summed up 
	 * and then subtracted from 200. Thus, a value between 200 and 150 will be the
	 * result. 
	 */
	private int improvedPosition(TDNode node){
		Vector<ScotlandJadeVertex> det = node.getDetectives();
		int mrx = node.getMrX();
		int sum = 0;
		for (int i = 0; i < det.size(); i++) {
			sum += df.getDistance(det.get(i), map.get(mrx));
		}
		return 200 - sum;
	}
	
	/**
	 * Looks if possible Mr X targets can be reached.
	 */
	private int reachedTarget(ScotlandJadeVertex det, ScotlandJadeVertex target){
//		ScotlandJadeVertex detectivePos = td.getCurrentDetectivePosition(options);
		
		List<ScotlandJadeVertex> reached = Graphs.neighborListOf(map, det);
		List<ScotlandJadeVertex> targetNeighbours = Graphs.neighborListOf(map, target);
		
		// for all neighbours of the detective position look if the target node is a neighbour,
		// means, if its reachable.
		for (int i = 0; i < reached.size(); i++) {
//			System.out.println("***meine liste is so lang: " + reached.size());
//			System.out.println("***watt steht denn da drin? " + reached.get(i).getIndex() + " " + target.getIndex());
			int bestStation = 0;
			
			// if its a neighbour
			if(reached.get(i).getIndex() == target.getIndex()){
				
				// and if this neighbour is a metrostation return the importance of this node, which is 
				// the highest value: 204
				if(td.getStationType(target) == 3){
//					System.out.println("======== he is on a metrostation");
					return 204;
				}
				
				// if this neighbour is a busstation return the second highest value.
				else if(td.getStationType(target) == 2){
//					System.out.println("======== he is on a busstation");
					return 203;
				}
				
				else {
					
					// if its just a taxi stop, look if there is an important neighbour around this node.
					for (int j = 0; j < targetNeighbours.size(); j++) {
						
						// either the neighbour is a metro station
						if(td.getStationType(targetNeighbours.get(j)) == 3){
//							System.out.println("======== he is IN ONE MOVE on a metrostation");
							bestStation = 202;
						}
						
						// or a busstation
						else if (td.getStationType(targetNeighbours.get(j)) == 2 && bestStation < 201){
//							System.out.println("======== he is IN ONE MOVE on a busstation");
							bestStation = 201;
						}
						
						// or just a taxi stop
						else if (bestStation < 201){
//							System.out.println("======== just taxi...");
							bestStation = 200;
						}
					}
//					System.out.println("ich returne die warnnummer: " + bestStation);
					// return the value of importance for this node
					return bestStation;
				}
			}
		}
//		System.out.println("======== i dont reach this node...");
		// if its not a reachable node for the detective return -1
		return -1;
	}

	/**
	 * This method finds the closest Metro Station to the current position of
	 * the Detective. It looks whether the detective is already on a
	 * metrostation. If yes, he should move to the next best taxi station to
	 * move back to this metro in the next round. If he is not already on a
	 * metrostation it will find, if there is one within 2 moves. Otherwise he
	 * will go to a bus stop with a lot of neighbours.
	 * 
	 * @return ScotlandJadeVertex value. The Vertex, to which the detective
	 *         should go.
	 */
	private ScotlandJadeVertex findClosestMetro() {

		// Declaration of the variables
		int howManyNeighbours = 0; // how many neighbours has the busstation
		ScotlandJadeVertex moveTo = null; // where to go to
		ScotlandJadeVertex detectivePos = td
				.getCurrentDetectivePosition(options); // current detective
		// position
		List<ScotlandJadeVertex> l = Graphs.neighborListOf(map, detectivePos); 
		
//		System.out.println("_________Laufe zu... "
//				+ moveTowards(map.get(74), map.get(47)));
		// if its round 1
		if (turn == 1) {
			System.out.println("ROUND #01");

			// and the detective is already at a metrostation
			if (td.getStationType(detectivePos) == 3) {

				// look for the next taxi stop and go there
				for (int i = 0; i < l.size(); i++) {
					if (td.getStationType(l.get(i)) == 1) {
						moveTo = l.get(i);
						return moveTo;
					}
				}
			}

			// if the detective is not at a metrostation
			else {

				// for every node in the neighbour list, create another list
				// with all
				// neighbours of these.
				for (int z = 0; z < l.size(); z++) {
					List<ScotlandJadeVertex> m = Graphs.neighborListOf(map, l
							.get(z));

					// for all those neighbours
					for (int y = 0; y < m.size(); y++) {

						// if there is a metro station in this list, go to the
						// vertex in the list above.
						if (td.getStationType(m.get(y)) == 3) {
							moveTo = l.get(z);
							return moveTo;
						}

						// if there is only a busstation available, look for
						// that one
						// with the most neighbours.
						if (td.getStationType(m.get(y)) == 2) {

							// create a list of all neighbours
							List<ScotlandJadeVertex> n = Graphs.neighborListOf(
									map, m.get(y));

							// if this list has more entries than the one
							// before, choose this
							// busstop
							if (howManyNeighbours < n.size()) {
								howManyNeighbours = n.size();
								moveTo = l.get(z);
							}
						}
					}
				}
				return moveTo;
			}
		}

		// if its the second round
		if (turn == 2) {
			System.out.println("ROUND #02");

			// and the detective is already at a metrostation
			if (td.getStationType(detectivePos) == 3) {

				// look for the next taxi stop and go there
				for (int i = 0; i < l.size(); i++) {
					if (td.getStationType(l.get(i)) == 1) {
						moveTo = l.get(i);
						return moveTo;
					}
				}
			}

			// for all neighbours of the detective
			for (int j = 0; j < l.size(); j++) {

				// look if there is only a busstop and choose the one with the
				// most neighbours to go
				if (td.getStationType(l.get(j)) == 2) {

					// create a list of all neighbours
					List<ScotlandJadeVertex> k = Graphs.neighborListOf(map, l
							.get(j));

					// if this list has more entries than the one before, choose
					// this
					// busstop
					if (howManyNeighbours < k.size()) {
						howManyNeighbours = k.size();
						moveTo = l.get(j);
					}
				}

				// if there is a metrostation go there
				if (td.getStationType(l.get(j)) == 3) {
					moveTo = l.get(j);
					return moveTo;
				}
			}
			return moveTo;

		}
		if (turn >= 3) {
			moveTo = blocking();
			return moveTo;
		}
		return moveTo;
	}

	/**
	 * Strategy that is used until the 3rd move.
	 */
	private ScotlandJadeVertex blocking() {
		List<ScotlandJadeVertex> mrx;
		ScotlandJadeVertex detectivePos = td
				.getCurrentDetectivePosition(options);
		int distance = 100;
		ScotlandJadeVertex goTo = map.get(0);
		// find the position of mr x now or where mrx can be in one move

		mrx = findMrX(true);

		for (int i = 0; i < mrx.size(); i++) {
			if (distance > df.getDistance(detectivePos, mrx.get(i))) {
				distance = df.getDistance(detectivePos, mrx.get(i));
				goTo = mrx.get(i);
//				System.out.println("Meine auswahl plus distanz " + goTo + distance);
			}
		}
//		System.out.println("______________ich werde gehen nach: " + goTo);
//		System.out.println("______________meine kleinste distanz ist: "
//				+ distance);
		if (distance > 1) {
			mrx.clear();
			mrx = findMrX(false);
			for (int i = 0; i < mrx.size(); i++) {
//				System.out.println("isch reschne, isch reschne....");
				if (distance > df.getDistance(detectivePos, mrx.get(i))) {
					distance = df.getDistance(detectivePos, mrx.get(i));
					goTo = mrx.get(i);
				}
			}
			if (distance > 1) {
//				System.out.println("------------_____ bin isch schon drin?");
				int whichNode = moveTowards(detectivePos, goTo);
				goTo = map.get(whichNode);
//				System.out.println("______________ich werde gehen nach: "
//						+ goTo);
				return goTo;
			}
			
		}
//		System.out.println("______________ich werde gehen nach: "
//				+ goTo);
		return goTo;
		// find the closest point from the detective to one of this point
		// go there
	}

	/**
	 * Gets closer to Mr. X.
	 * @param from is the start
	 * @param to is the goal
	 * The methos finds the neighbour of ScotlandJadeVertex from that is closest 
	 * to ScotlandJadeVertex to.
	 */
	private int moveTowards(ScotlandJadeVertex from, ScotlandJadeVertex to) {
		List<ScotlandJadeVertex> neighbourList = Graphs.neighborListOf(map,
				from);
		int distance = 100;
		int bestPlace = -1;
		for (int i = 0; i < neighbourList.size(); i++) {
			if (df.getDistance(neighbourList.get(i), to) < distance) {
				distance = df.getDistance(neighbourList.get(i), to);
				bestPlace = i;
			}
		}
		return neighbourList.get(bestPlace).getIndex();
	}
	
	/**
	 * This method finds the current possible positions of mrx plus the possible
	 * nodes where he can go to in the next move
	 * 
	 * @return a scotlandJadeVertex list, with the possible positions of mrX
	 */
	private List<ScotlandJadeVertex> findMrX(boolean flag) {

		int depth = (td.getRound() - 3) % 5;
		if (flag == true) {
			// If its the round where Mr. X shows himself
			if (depth == 0) {

				// clear our lists
				td.mrx.clear();
				td.mrxFuture.clear();

				// put all neighbours of the curretn Mr.X position into the
				// mrxFuture list
				td.mrxFuture = Graphs.neighborListOf(map, map
						.get(lastKnownFugitivePosition));

				// add Mr. X's current position into the list of these.
				td.mrx.add(map.get(lastKnownFugitivePosition));

				// ----------------Tests----------------
				// System.out.println("‡‡‡‡‡‡‡‡‡‡‡‡");
				// System.out.println("ROUND3 " + mrx);
				//			
				// for (int i = 0; i < mrxFuture.size(); i++) {
				// System.out.println( " " + mrxFuture.get(i));
				// }
				// ----------------Tests----------------

				// return the current position of Mr. X
				return td.mrx;
			} else {

				// ----------------Tests----------------
				// for (int i = 0; i < mrxFuture.size(); i++) {
				// System.out.println("‡‡‡mrxFuture vorher: "+mrxFuture.get(i));
				// }
				// ----------------Tests----------------

				int transport = 0;
				int t = 0;

				// find out which transportation Mr. X used
				transport = td.lastKnownFugitiveTransports
						.get(td.lastKnownFugitiveTransports.size() - 1);
				// System.out.println("----------------TRANSPORT???? " +
				// transport);

				// falls in der mrx liste ein knoten drin ist, der nicht mit dem
				// ticket übereinstimmt remove ihn
				Vector<ScotlandJadeVertex> deleteIndex = new Vector<ScotlandJadeVertex>();

				// if Mr. X used a black ticket
				if (transport == 60) {
					System.out.println(" ");
					System.out.println("______BLACKTICKET");

					// set all nodes where a detective already stands on into
					// the deleteIndex list
					for (int i = 0; i < td.mrxFuture.size(); i++) {
						if (td.mrxFuture.get(i).getType() == Type.DETECTIVE) {
							System.out.println("remove " + td.mrxFuture.get(i));

							// add this vertex to the deleteIndex list
							deleteIndex.add(td.mrxFuture.get(i));
						}
					}
				} else {
					// for every node in the current possible Mr. X position
					// list
					for (int j = 0; j < td.mrx.size(); j++) {

						// find out the neighbours
						List<ScotlandJadeVertex> neighbours = Graphs
								.neighborListOf(map, td.mrx.get(j));

						// for every node where Mr. X can b in one move
						for (int m = 0; m < td.mrxFuture.size(); m++) {

							// and for every neighbour of the current Mr. X
							// position
							for (int n = 0; n < neighbours.size(); n++) {

								// if these 2 nodes are similar
								if (td.mrxFuture.get(m).getIndex() == neighbours
										.get(n).getIndex()) {
									// System.out.println("‡‡‡ " +
									// mrxFuture.get(m).getIndex() +" " +
									// neighbours.get(n).getIndex());

									t = map.getEdge(td.mrx.get(j),
											td.mrxFuture.get(m)).getType();
									// System.out.println("‡‡‡typ " + t
									// +" "+transport);

									// and if the transportationtype is
									// different or a detective is already on
									// that node
									if (t != transport
											|| td.mrxFuture.get(m).getType() == Type.DETECTIVE) {
										// System.out.println("remove "+mrxFuture.get(m));

										// add this vertex to the deleteIndex
										// list
										deleteIndex.add(td.mrxFuture.get(m));
									}
								}
							}
						}
					}
				}
//				System.out.println("listengröße vorm löschen: "
//						+ td.mrxFuture.size());
				// for (int i = 0; i < mrxFuture.size(); i++) {
				// System.out.println("meine liste vorm löschen!" +
				// mrxFuture.get(i));
				// }

				// delete every node out of mrxFuture which is in the
				// deleteIndex list
				for (int i = 0; i < deleteIndex.size(); i++) {
//					System.out.println("+remove " + deleteIndex.get(i));
					td.mrxFuture.remove(deleteIndex.get(i));
				}

//				System.out.println("listengröße nachm löschen: "
//						+ td.mrxFuture.size());
//				for (int i = 0; i < mrxFuture.size(); i++) {
//					System.out.println("meine Liste nach dem löschen: "
//							+ mrxFuture.get(i));
//				}

				// falls es runde 1 nach dem erscheinen is remove die
				// lastknownfugitiveposition
				// lass alle nachbarknoten ausgeben

				// clear the list with the current possible nodes of Mr. X
				td.mrx.clear();

				// write the future nodes of Mr. X into the current position
				// list, because these are now
				// the new possible positions of Mr. X.
				for (int i = 0; i < td.mrxFuture.size(); i++) {
					td.mrx.add(td.mrxFuture.get(i));
				}

				// clear the list with the future nodes
				td.mrxFuture.clear();

				// write the new neighbours in the future Mr. X positionslist.
				List<ScotlandJadeVertex> currentNeighbours;
				for (int k = 0; k < td.mrx.size(); k++) {
					currentNeighbours = Graphs.neighborListOf(map, td.mrx.get(k));
					for (int l = 0; l < currentNeighbours.size(); l++) {
						td.mrxFuture.add(currentNeighbours.get(l));
					}
				}

				// delete redundancies in the list.
				td.mrxFuture = deleteRedundancies(td.mrxFuture);

				// // This keeps the possible nodes beyond 11 !!!!!!!!!!!!!!!!
				// // Otherwise the calculation is too heavy.
				// // Later here is has to be a selection of the 10 to 20 best
				// targets.
				// while(mrxFuture.size() > 10){
				// mrxFuture.remove(mrxFuture.size()-1);
				// System.out.println("removed...");
				// }

				// for (int i = 0; i < mrxFuture.size(); i++) {
				// System.out.println("‡‡‡mrxFuture am ende: "+mrxFuture.get(i));
				// }

			}
			Vector<ScotlandJadeVertex> detPositions = td.getDetectivePositions();
			for (int i = 0; i < detPositions.size(); i++) {
				for (int j = 0; j < td.mrx.size(); j++) {
					if(detPositions.get(i).getIndex() == td.mrx.get(j).getIndex()){
						td.mrx.remove(j);
					}
				}
			}
			td.mrx = findBestMrXPositions();
			if(td.mrx.size()==0){
				td.mrx = td.mrxFuture;
			}
			return td.mrx;
		} else {
//			System.out.println("bin in else");
			for (int i = 0; i < td.mrxFuture.size(); i++) {
//				System.out.println("mrxFuture: " + td.mrxFuture.get(i));
			}
			return td.mrxFuture;
		}

		// falls mrx nich grad erst aufgetaucht is
	}

	/**
	 * Reduces the mrx list to the best targets, which includes different strategies of Mr X.
	 */
	private List<ScotlandJadeVertex> findBestMrXPositions() {
//			Vector for all vertices where detectives are.
		Vector<ScotlandJadeVertex> detPositions = td.getDetectivePositions();
//			Vector where the targets of the different detectives are saved later.
//			A target is a possible place where MrX can be right now.
//		int[] detTargets = new int[detPositions.size()];
		List<ScotlandJadeVertex> detTargets = Graphs.neighborListOf(map, map.get(1));
		detTargets.clear();
//			Array for already chosen targets of detectives.
//			This arranges, that all detectives have different places to go.
//			Surrounding and blocking appears often because of this array.
		Vector<Integer> inUse = new Vector<Integer>();
		
//			Targets get assigned to all detectives.
//			Usage of one target gets written into inUse.
		for (int i = 0; i < detPositions.size(); i++) {
			detTargets.add(findTarget(detPositions.get(i), inUse));
			inUse.add(detTargets.get(detTargets.size()-1).getIndex());
		}
		
		int[] distanceValues = new int[td.mrx.size()];
		int value = 0;
		for (int i = 0; i < td.mrx.size(); i++) {
			for (int j = 0; j < detTargets.size(); j++) {
				value += df.getDistance(td.mrx.get(i), detTargets.get(j));
			}
			distanceValues[i] = value;
			value = 0;
		}
		int highest = 0;
		int index = 0;
		for (int i = 0; i < distanceValues.length; i++) {
			if(highest < distanceValues[i]){
				highest = distanceValues[i];
				index = i;
			}
		}
		int lowestDist = 100;
		int index2 = 0;
		for (int i = 0; i < detPositions.size(); i++) {
			if(td.mrx!=null){
				if(df.getDistance(detPositions.get(i), td.mrx.get(index)) < lowestDist){
					lowestDist = df.getDistance(detPositions.get(i), td.mrx.get(index));
					index2 = i;
				}
			}
		}
		
		List<ScotlandJadeVertex> detTargets2 = Graphs.neighborListOf(map, map.get(1));
		detTargets2.clear();
		for (int i = 0; i < detTargets.size(); i++) {
			if(td.mrx!=null){
				if(i == index2){
					detTargets2.add(td.mrx.get(index));
				}else{
					detTargets2.add(detTargets.get(i));
				}
			}
		}
		return detTargets2;
	}
	
	/**
	 * Best approaching target by two certain positions.
	 */
	private ScotlandJadeVertex findTarget(ScotlandJadeVertex pos, Vector<Integer> inUse){
		int distance = 100;
		int current;
		int listPosition = 0;
		boolean isUsed = false;
		for (int i = 0; i < td.mrx.size(); i++) {
			current = df.getDistance(pos, td.mrx.get(i));
			if(current < distance){
				for (int j = 0; j < inUse.size(); j++) {
					if(inUse.get(j) == td.mrx.get(i).getIndex()){
						isUsed = true;
					}
				}
				if(!isUsed){
					distance = current;
					listPosition = i;
				}else{
					if(inUse.size() == td.mrx.size()){
						distance = current;
						listPosition = i;
					}
				}
			}
			isUsed = false;
		}
		return td.mrx.get(listPosition);
	}
	
	/**
	 * Best blocking target by two certain positions.
	 */
	private ScotlandJadeVertex findSecondTarget(ScotlandJadeVertex pos, Vector<Integer> inUse){
		int distance = 100;
		int current;
		int listPosition = 0;
		int listPosition2 = 0;
		boolean isUsed = false;
		for (int i = 0; i < td.mrx.size(); i++) {
			current = df.getDistance(pos, td.mrx.get(i));
			if(current < distance){
				for (int j = 0; j < inUse.size(); j++) {
					if(inUse.get(j) == td.mrx.get(i).getIndex()){
						isUsed = true;
					}
				}
				if(!isUsed){
					distance = current;
					listPosition = i;
				}else{
					if(inUse.size() == td.mrx.size()){
						distance = current;
						listPosition = i;
					}
				}
			}
			isUsed = false;
		}
		
		for (int i = 0; i < td.mrx.size(); i++) {
			current = df.getDistance(pos, td.mrx.get(i));
			if(current < distance){
				for (int j = 0; j < inUse.size(); j++) {
					if(inUse.get(j) == td.mrx.get(i).getIndex()){
						isUsed = true;
					}
				}
				if(!isUsed && i!=listPosition){
					distance = current;
					listPosition2 = i;
				}else{
					if(inUse.size() == td.mrx.size()){
						distance = current;
						listPosition2 = i;
					}
				}
			}
			isUsed = false;
		}
//		TODO
		return td.mrx.get(listPosition);
	}
	
	/**
	 * Deletes reduntant nodes from the list of nodes (for example in the list
	 * of possible positions of Mr. X). When there is node 86 two time in the
	 * list, one will be deleted.
	 */
	private List<ScotlandJadeVertex> deleteRedundancies(
			List<ScotlandJadeVertex> openList) {
		List<ScotlandJadeVertex> list2 = Graphs.neighborListOf(map, map.get(1));
		list2.clear();
		boolean isNew;
		for (int i = 0; i < openList.size(); i++) {
			isNew = true;
			for (int j = 0; j < list2.size(); j++) {
				if (list2.get(j).getIndex() == openList.get(i).getIndex()) {
					isNew = false;
				}
			}
			if (isNew) {
				list2.add(openList.get(i));
				isNew = false;
			}
		}
		return list2;
	}
	
	/**
	 * Gives the agent another move option, that is not about approaching, but about creating a wall with other detectives.
	 */
	private int alternativeMoveOption(ScotlandJadeVertex detPosition, ScotlandJadeVertex detTarget, ScotlandJadeVertex used) {
		List<ScotlandJadeVertex> neighbours = Graphs.neighborListOf(map, detPosition);
		int index = 0;
		int lowest = 100;
		for (int i = 0; i < neighbours.size(); i++) {
			if(df.getDistance(neighbours.get(i), detTarget) < lowest){
				lowest = df.getDistance(neighbours.get(i), detTarget);
				index = i;
			}
		}
		return neighbours.get(index).getIndex();
	}
}
